|
|
Tennenbaum phenomena in models of arithmetic
Kriško, Lukáš ; Thapen, Neil (advisor) ; Bulín, Jakub (referee)
The main aim of this text is to present and investigate some basic arithmetical func- tions and relations with regard to being recursive in a countable non-standard model of Peano arithmetic, PA for short, or some weaker fragment, like I∆0 or IΣ1, of PA. In PART I, we present a known result called Tennenbaum's theorem. It states that every non-standard model M of PA with domain N can have neither +M nor ×M recursive. Moreover, we present the case for + in a strengthened version for I∆0, which is due to K. McAloon. To show that not everything is lost, we also present a well know result stating that < and the successor function can be simultaneously recursive in some non-standard model of PA with domain N. In PART II, we make our own investigation into the questions related to whether there can be a non-standard model of PA s.t. x div y, the quotient function, and x mod y, the remainder function, are recursive in it. Furthermore, we often restrict y to some standard number n. To give a non-exhaustive list of problems we have solved, we showed that there can be no non-standard model of PA with both x div n and x mod n recursive. Furthermore, there can be no non-standard model of IΣ1 with x div y recursive. On the other hand, x div n and x mod n can be separately recursive in a non-standard model of PA. 1
|
guest ::
